// @algorithm @lc id=1000235 lang=cpp
// @title 7p8L0Z

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        dfs(nums, n, 0);
        return ans;
    }
    void dfs(vector<int> &nums, int n, int level) {
        if (level == n) {
            ans.push_back(nums);
            return;
        }
        unordered_set<int> hash_table;
        for (int k = level; k < n; ++k) {
            if (hash_table.find(nums[k]) != hash_table.end()) {
                continue;
            }
            hash_table.insert(nums[k]);
            swap(nums[level], nums[k]);
            dfs(nums, n, level + 1);
            swap(nums[level], nums[k]);
        }
    }
};